﻿//2389. 和有限的最长子序列
//给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
//返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。
//子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。


class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries)
    {
        int n = nums.size();
        int m = queries.size();
        vector<int> prev(n);
        int sum = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++)
        {
            sum += nums[i];
            prev[i] = sum;
        }
        vector<int> ans(m);
        for (int i = 0; i < m; i++)
        {
            ans[i] = upper_bound(prev.begin(), prev.end(), queries[i]) - prev.begin();
        }
        return ans;
    }
};